package com.simon.study.algorithm.zheda;

import com.simon.study.algorithm.tree.TNode;
import com.simon.study.algorithm.tree.TNode.HNode;
import com.simon.study.algorithm.tree.Tree;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import lombok.Getter;
import lombok.Setter;
import lombok.experimental.Accessors;

/**
 * <p>
 *
 * @author simon
 * @date 2022/9/2 5:03 下午
 */
@Getter @Setter @Accessors(chain = true)
public class HuffmanTree {

    public static final int MAXSIZE = 1000;

    HNode[] nodes;
    int     size;
    int     capacity;


    public HuffmanTree(int capacity) {
        this.capacity   = capacity;
        this.nodes      = new HNode[capacity];
    }

    // minheap
    public void heapify(int index){
        HNode tar = nodes[index]; int left = (index<<1) + 1;

        while (left < size){
            if( left+1 < size && nodes[left+1].getWeight() < nodes[left].getWeight() ){
                left++;
            }

            if(nodes[left].getWeight() > tar.getWeight()){ break; }

            nodes[index] = nodes[left];
            index = left; left = (index<<1) + 1;
        }

        nodes[index] = tar;
    }

    public HNode delete(){
        HNode deleted = nodes[0];
        nodes[0] = nodes[--size];
        heapify(0);
        return deleted;
    }

    public void adjust(){
        int half = (size-1)/2;

        for (int i = half; i >= 0; i--) { heapify(i); }
    }


    public void insert(HNode node){
        int index = size++;
        while( index > 0 && node.getWeight() < nodes[(index-1)/2].getWeight() ){
            nodes[index] = nodes[(index-1)/2];
            index = (index-1)/2;
        }
        nodes[index] = node;
    }


    public TNode build(){
        int times = size;
        for (int i = 1; i < times; i++) {

            HNode node = new HNode();
            node.setLeft( delete() );
            node.setRight( delete() );
            node.setWeight( node.getLeft().getWeight() + node.getRight().getWeight() );
            insert(node);
        }
        return delete();
    }

    public void create(int[] weights){
        for (int i = 0; i < weights.length; i++) {
            nodes[i] = new HNode(weights[i]);
        }
        this.size = weights.length;
        adjust();
    }

    public int[] getWeights(){
        int[] arr = new int[size];

        for (int i = 0; i < size; i++) {
            arr[i]  = nodes[i].getWeight();
        }
        return arr;
    }

    public static void main(String[] args) {
        HuffmanTree htree = new HuffmanTree(30);
        // test insert and adjust
        int[] arr = {13,1,45,7,20,4,19,13,40,33,38};
        for (int i = 0; i < arr.length; i++) {
            htree.insert(new HNode(arr[i]));
        }
        System.out.println(Arrays.toString(htree.getWeights()));

        int[] arr1 = {13,1,45,7,20,4,19,13,40,33,38};
        htree.create(arr1);
        System.out.println(Arrays.toString(htree.getWeights()));

        Tree tree = new Tree(htree.build());
        System.out.println(Arrays.toString(htree.getWeights()));

        tree.hiarachicallyPrint();
        huffDfs((HNode) tree.getRoot());
    }

    public static void huffDfs(HNode node){
        Deque<HNode> stack = new ArrayDeque<>();
        stack.push(node);

        Deque<char[]> ls = new ArrayDeque<>();
        ls.push(new char[0]);
        while (!stack.isEmpty()){

            HNode tmp   = stack.pop();
            char[] ctmp = ls.pop();

            int cs      = stack.size();

            if( tmp.getRight() != null ){
                stack.push(tmp.getRight());

                char[] cdup = Arrays.copyOf(ctmp, ctmp.length+1);
                cdup[cdup.length-1] = '1';
                ls.push(cdup);
            }

            if( tmp.getLeft() != null ){
                stack.push(tmp.getLeft());

                char[] cdup = Arrays.copyOf(ctmp, ctmp.length+1);
                cdup[cdup.length-1] = '0';
                ls.push(cdup);
            }

            // leaf
            if( cs == stack.size() ){
                System.out.println(new String(ctmp) + ":" + HNode.sweight(tmp));
            }
        }
    }
}
